Pada 23 Julai 2001, Dewan Perundingan Rakyat (MPR) menyingkirkan Wahid dari pejabat dan, pada hari yang sama, bersumpah kepada Megawati sebagai presiden baru.[17] Oleh itu, beliau menjadi wanita keenam untuk memimpin negara majoriti Muslim, selepas Benazir Bhutto dari Pakistan, Khaleda Zia, Bangladesh, Tansu Çiller dari Turki, Hasina Wajed dari Bangladesh dan Mame Madior Boye dari Senegal.

Kebangkitan ikon pembangkang terhadap rejim Suharto ke jawatan presiden pada awalnya dialu-alukan secara meluas, tetapi tidak lama kemudian menjadi jelas bahawa jawatan presidennya ditandakan dengan tidak ragu-ragu, kekurangan arah ideologi yang jelas, dan "reputasi untuk tidak bertindak terhadap isu-isu dasar yang penting".[18][19][20] Sisi baik kemajuan yang perlahan pembaharuan dan mengelakkan konfrontasi adalah bahawa beliau menstabilkan keseluruhan proses pendemokrasian dan hubungan antara perundangan, eksekutif, dan tentera.[18]

Beliau bertanding untuk pemilihan semula pada tahun 2004 dalam pilihan raya presiden langsung pertama negara itu, dengan harapan agar menjadi wanita pertama yang dipilih sebagai hak negara sebagai negara majoriti Muslim. Bagaimanapun, beliau tewas di tangan Susilo Bambang Yudhoyono dalam pusingan kedua, 61 peratus kepada 39 peratus,[17] pada 20 September 2004. Beliau tidak menghadiri perasmian presiden baru, dan tidak pernah mengucapkan tahniah kepadanya.[21]